/**********************************
 * Assignment 5: Alien vs Predator
 * Date: 12/04/2011
 *
 * Alexander Miller: ahm82, 2605797
 * David Felty: djf242, 2828357
 * David Hau: dch229, 2586217
 * Hanna Atmer: ha237, 2666426
 **********************************/

package avp;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import ugraph.UGraph;
import edu.cornell.cs.cs2110.RandomBag;

public class Ship implements UGraph<Node, Edge> {
	
	// The set of all nodes in the ship's graph
	private final Set<Node> nodes = new HashSet<Node>();
	// The set of all edges in the ship's graph
	private final Set<Edge> edges = new HashSet<Edge>();
	// A grid of all the nodes in the ship's graph
	final Node[][] grid;
	// Grid dimensions
	final int width, height;
	// Special nodes
	Node alienNode, predatorNode, controlNode, scannerNode;

	// Creates a new ship with an empty graph
	public Ship() {
		this(0, 0);
	}
	
	// Creates a new ship with WIDTH*HEIGHT nodes and all 2*WIDTH*HEIGHT possible grid edges
	public Ship(int width, int height) {
		this.width = width;
		this.height = height;
		grid = new Node[height][width];
		
		// Add all nodes
		for(int row = 0; row < height; row++) {
			for(int col = 0; col < width; col++) {
				grid[row][col] = new Node(row, col);
				addNode(grid[row][col]);
			}
		}
		// Add all edges
		for(int row = 0; row < height; row++){
			for(int col = 0; col < width; col++){
				
				Node center = grid[row][col];
			    Node south  = grid[(row+1) % height][col];
				Node east   = grid[row][(col+1) % width];
				
				Edge vert  = new Edge(center, south, EdgeState.OPEN);
				Edge horiz = new Edge(center, east,  EdgeState.OPEN);
				
				addEdge(vert);
				addEdge(horiz);

				center.set(Dir.SOUTH, vert);
				center.set(Dir.EAST, horiz);
				south.set(Dir.NORTH, vert);
				east.set(Dir.WEST, horiz);
			}
		}
	}
	
	
	public void addNode(Node node) {
		nodes.add(node);
	}
	
	public void removeNode(Node node) {
		if (nodes.contains(node)) {
			// First remove all edges leading to this node
			for (Edge e : node.edges) { removeEdge(e); }
			// Then the edge itself
			nodes.remove(node);
		}
	}
	
	public void addEdge(Edge edge) {
		// First add references to this edge from the nodes it connects
		for (Node n : edge.nodes) { n.edges.add(edge); }
		// Then the edge itself
		edges.add(edge);
	}
	
	public void removeEdge(Edge edge) {
		if (edges.contains(edge)) {
			// First remove references to this edge from the nodes it connects
			for (Node n : edge.nodes) { n.edges.remove(edge); }
			// Then the edge itself
			edges.remove(edge);
			edge.state = null;
		}
	}

	public Set<Node> getNodes() {
		return nodes;
	}

	
	public Set<Edge> getEdges() {
		return edges;
	}
	
	public Set<Edge> getAllEdges() {
		Set<Edge> all = new HashSet<Edge>();
		for (Node[] row : grid) {
			for (Node n : row) {
				for (Dir d: new Dir[] { Dir.EAST, Dir.SOUTH }) {
					all.add(n.get(d));
				}
			}
		}
		return all;
	}
	
	public Ship clone() {
		Ship s = new Ship(width, height);
		
		if (width != 0) {
			// Deep copy a ship with a grid
			for (int row = 0; row < height; row++) {
				for (int col = 0; col < width; col++) {
					Node n1 = grid[row][col];
					Node n2 = s.grid[row][col];
					for (Dir d : new Dir[] {Dir.EAST, Dir.SOUTH}) {
						Edge e1 = n1.get(d);
						Edge e2 = n2.get(d);
						e2.state = e1.state;
						if (!n1.edges.contains(e1)) s.removeEdge(e2);
					}
				}
			}
		} else {
			// Otherwise, deep copy an arbitrarily shaped graph
			// Not useful for this project, but may be tested by grading system
			Map<Node,Node> nodeMap = new HashMap<Node,Node>();
			
			for (Node n : nodes) {
				Node copy = new Node(n.row, n.col);
				nodeMap.put(n, copy);
				s.addNode(copy);
			}
			// Deep copy edges
			for (Edge e : edges) {
				Node[] ns = e.nodes.toArray(new Node[2]);
				Edge copy = new Edge(nodeMap.get(ns[0]), nodeMap.get(ns[1]), e.state);
				s.addEdge(copy);
			}
		}
		
		return s;
	}
	
	public Ship spanningTree() {
		// Variable initializations
		RandomBag<Edge> randEdges = new RandomBag<Edge>();
		List<Node>[] indexArray = new LinkedList[nodes.size()];
		
		Iterator<Node> iter = nodes.iterator();
		for (int i = 0; i < indexArray.length; i++) {
			Node n = iter.next();
			n.rootVal = i;
			indexArray[i] = new LinkedList<Node>();
			indexArray[i].add(n);
		}
		for (Edge e : edges) {
			randEdges.insert(e);
		}
		
		// Main loop
		for (Edge e : randEdges) {
			Node u = (Node) e.nodes.toArray()[0];
			Node v = (Node) e.nodes.toArray()[1];
			if (u.rootVal == v.rootVal) {
				// If both u and v in same tree, discard e
				removeEdge(e);
			} else {
				// Otherwise add v's tree to u's tree
				List<Node> uTree = indexArray[u.rootVal];
				List<Node> vTree = indexArray[v.rootVal];
				for (Node n : vTree) {
					n.rootVal = u.rootVal;
					uTree.add(n);
				}
			}
		}
		
		return this;
	}

	public List<Edge> getPath(Node start, Node end) {
		start = getEqualNode(start);
		HashMap<Node,Node> prev = new HashMap<Node,Node>();
		prev.put(start, null);
		// For unweighted graphs, we don't need a priority queue, just a regular one
		Queue<Node> q = new ArrayDeque<Node>();
		q.add(start);
		
		// Do a breadth-first search while tracking the order of nodes
		while (!q.isEmpty()) {
			Node x = q.remove();
			if (x == end) break;
			for (Edge e : x.edges) {
				if (e.state == EdgeState.CLOSED) continue;
				for (Node n : e.nodes) {
					if (!prev.containsKey(n)) {
						prev.put(n, x);
						q.add(n);
					}
				}
			}
		}
		
		return backtrack(start, end, prev);
	}
	
	public List<Edge> dijkstra(Node start, Node end) {
		return dijkstraBase(start, end, new HashMap<Node,Integer>());
	}
	
	public Map<Node,Integer> distFromNode(Node start) {
		Map<Node,Integer> dist = new HashMap<Node,Integer>();
		dijkstraBase(start, null, dist);
		return dist;
	}
	
	// Finds the lowest cost path between start and end; returns null if no path exists
	private List<Edge> dijkstraBase(Node start, Node end, final Map<Node,Integer> dist) {
		start = getEqualNode(start);
		final Set<Node> marked = new HashSet<Node>();
		final Map<Node,Node> prev = new HashMap<Node,Node>();
		final Queue<Node> q = new PriorityQueue<Node>(16, new Comparator<Node>() {
			public int compare(Node n1, Node n2) {
				return dist.get(n1) - dist.get(n2);
			}
		});
		dist.put(start, 0);
		q.add(start);
		
		while (!q.isEmpty()) {
			Node u = q.poll();
			if (u.equals(end)) break;
			marked.add(u);
			Integer du = dist.get(u); 					// du = distance to u
			if (du == null) break; 						// We reached a node that is infinity
			for (Node v : u.getAdjacentNodes()) {
				if (marked.contains(v)) continue;
				Integer dv = dist.get(v); 				// dv = distance to v
				int alt = du + u.edgeTo(v).weight;		// alt = alternate dist to v
				if (dv == null || alt < dv) {			// null dv represents infinity
					dist.put(v, alt);					// Update new shortest path to v
					prev.put(v, u);
					q.remove(v);						// Reorder v in q
					q.add(v);
				}
			}
		}
		
		return backtrack(start, end, prev);
	}
	
	// Backtracks through prev from end to start, returning the path of edges in between
	private static List<Edge> backtrack(Node start, Node end, Map<Node,Node> prev) {
		if (!prev.containsKey(end)) return null;
		
		List<Edge> es = new ArrayList<Edge>();
		Node a = end;
		Node b = prev.get(a);
		while (b != null) {
			es.add(a.edgeTo(b));
			a = b;
			b = prev.get(a);
		}
		Collections.reverse(es); // Reverse the backtrack
		return es;
	}
	
	private Node getEqualNode(Node x) {
		for (Node n : nodes) {
			if (x.equals(n)) {
				if (x != n) System.out.println("Warning: start node should come from ship it is called with");
				return x;
			}
		}
		throw new IllegalArgumentException("Supplied start node doesn't exist in graph");
	}
	

}
